/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._35;

/**
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 输入: [1,3,5,6], 5
 * 输出: 2
 *
 * 输入: [1,3,5,6], 2
 * 输出: 1
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._35
 * @ClassName: SearchInsertPosition
 * @Author: linyaonan
 * @Date: 2019/10/15 17:47
 */
public class SearchInsertPosition {

    public int searchInsert(int[] nums, int target) {
        // 数组为null或者空数组
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int numLength = nums.length;
        // 数组长度为1是特殊处理
        if (numLength == 1) {
            if (target <= nums[0]) {
                return 0;
            } else {
                return 1;
            }
        }
        if (target > nums[numLength - 1]) {
            return numLength;
        }
        if (target <= nums[0]) {
            return 0;
        }
        // 处理通用数组处理
        int lNum = 0;
        int rNum = nums.length - 1;
        while (true) {
            if (lNum == rNum || rNum - lNum == 1) {
                return rNum;
            } else {
                int tempIndex = ((rNum - lNum) / 2) + lNum;
                int tempNum = nums[tempIndex];
                if (tempNum == target) {
                    return tempIndex;
                }
                if (tempNum > target) {
                    rNum = tempIndex;
                } else {
                    lNum = tempIndex;
                }
            }
        }
    }

    public int searchInsert2(int[] nums, int target) {
        // 1. 边界
        if (nums[0] >= target) {
            return 0;
        }
        if (nums[nums.length - 1] <= target) {
            return nums.length;
        }
        // 2. 最左匹配，找到大于等于目标值的索引
        int l = 0;
        int r = nums.length - 1;
        int tt = -1;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (nums[m] >= target) {
                tt = m;
                r = m;
            } else {
                l = m + 1;
            }
        }

        return tt == -1 ? l : tt;
    }

    public int searchInsert3(int[] nums, int target) {
        // 1. 边界
//        if (nums[0] >= target) {
//            return 0;
//        }
//        if (nums[nums.length - 1] <= target) {
//            return nums.length;
//        }

        int l = 0;
        int r = nums.length - 1;
        int tt = -1;

        while (l <= r) {
            int m = (l + r) >>> 1;
            int temp = nums[m];
            if (temp == target) {
                tt = m;
                r = m - 1;
            } else if (temp < target) {
                l = m + 1;
            } else {
                tt = m;
                r = m - 1;
            }
        }

        return tt == -1 ? l : tt;
    }
}
